#include <stdlib.h>
#include <string.h>

#include "bitree.h"

/* name: bitree_init
 */
void bitree_init(BiTree *tree, void (*destroy)(void *data))
{
  /* Initialize the binary tree */

  tree->size = 0;
  tree->destroy = destroy;
  tree->root = NULL;

  return;
}

/*name: bitree_destroy
 */
void bitree_destroy(BiTree *tree)
{
  /* Remove all the nodes from the tree */
  bitree_rem_left(tree, NULL);

  /* No operations are allowed now, */
  /* but clear the structure as a precaution */
  memset(tree, 0, sizeof(BiTree));

  return;
}

/* name: bitree_ins_left
 */
int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data)
{
  BiTreeNode *new_node;
  BiTreeNode **position;

  /* Determine where to insert the node */
  if (NULL == node) {
    /* Allow insertion at the root only in an empty tree */
    if (bitree_size(tree) > 0)
      return -1;

    position = &tree->root;
  } else {
    /* Normally allow insertion only at the end of a branch */
    if (bitree_left(node) != NULL)
      return -1;

    position = &node->left;
  }
  
  /* Allocate storage for the node */
  if (NULL == (new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))))
    return -1;

  /* Insert the node into the tree */
  new_node->data = (void *)data;
  new_node->left = NULL;
  new_node->right = NULL;
  *position = new_node;

  /* Adjust the size of the tree to account for the inserted node */
  tree->size++;

  return 0;
}

/* name: bitree_ins_right
 */
int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data)
{
  BiTreeNode *new_node;
  BiTreeNode **position;

  /* Determine where to insert the node */
  if (NULL == node) {
    /* Allow insertion at the root only in an empty tree */
    if (bitree_size(tree) > 0)
      return -1;

    position = &tree->root;
  } else {
    /* Normally allow insertion only at the end of a branch */
    if (bitree_right(node) != NULL)
      return -1;

    position = &node->right;
  }

  /* Allocate storage for the node */
  if (NULL == (new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))))
    return -1;

  /* Insert the node into the tree */
  new_node->data = (void *)data;
  new_node->left = NULL;
  new_node->right = NULL;
  *position = new_node;

  /* Adjust the size of the tree to account for the inserted node */
  tree->size++;

  return 0;
}

/* name: bitree_rem_left
 */
void bitree_rem_left(BiTree *tree, BiTreeNode *node)
{
  BiTreeNode **position;

  /* Do not allow removal from an empty tree */
  if (0 == bitree_size(tree))
    return;

  /* Determine where to remove nodes */
  if (NULL == node)
    position = &tree->root;
  else
    position = &node->left;

  /* Remove the nodes */
  if (*position != NULL) {
    bitree_rem_left(tree, *position);
    bitree_rem_right(tree, *position);

    if (tree->destroy != NULL) {
      /* Call a user-defined function to free dynamically allocated data */
      tree->destroy((*position)->data);
    }

    free(*position);
    *position = NULL;
    
    /* Adjust the size of the tree to account for the removed node */
    tree->size--;
  }
  
  return;
}

/* name: bitree_rem_right
 */
void bitree_rem_right(BiTree *tree, BiTreeNode *node)
{
  BiTreeNode **position;

  /* Do not allow removal from an empty tree */
  if (0 == bitree_size(tree))
    return;

  /* Determine where to remove nodes */
  if (NULL == node)
    position = &tree->root;
  else
    position = &node->right;

  /* Remove the nodes */
  if (*position != NULL) {
    bitree_rem_left(tree, *position);
    bitree_rem_right(tree, *position);

    if (tree->destroy != NULL) {
      /* Call a user-defined function to free dynamically allocated data */
      tree->destroy((*position)->data);
    }

    free(*position);
    *position = NULL;

    /* Adjust the size of the tree to account for the removed node */
    tree->size--;
  }
  
  return;
}

/* name: bitree_merge
 */
int bitree_merge(BiTree *merge, BiTree *left, BiTree *right,
		 const void *data)
{
  /* Initialize the merged tree */
  bitree_init(merge, left->destroy);

  /* Insert the data for the root node of the merged tree */
  if (bitree_ins_left(merge, NULL, data) != 0) {
    bitree_destroy(merge);
    return -1;
  }

  /* Merge the two binary trees into a single binary tree */
  bitree_root(merge)->left = bitree_root(left);
  bitree_root(merge)->right = bitree_root(right);

  /* Adjust the size of the new binary tree */
  merge->size = merge->size + bitree_size(left) + bitree_size(right);

  /* Do not let the original trees access the merged nodes */
  left->root = NULL;
  left->size = 0;
  right->root = NULL;
  right->size = 0;

  return 0;
}
